home *** CD-ROM | disk | FTP | other *** search
/ MacHack 2000 / MacHack 2000.toast / pc / The Hacks / Softshoe / Lisa's Portable Parts / BitArray / Bits.cp < prev    next >
Encoding:
Text File  |  2000-06-23  |  5.0 KB  |  173 lines
  1. // Bits.cp
  2.  
  3. #ifndef Bits_h
  4. #include "Bits.h"
  5. #endif
  6. #ifndef SplitIntegers_h
  7. #include "SplitIntegers.h"
  8. #endif
  9.  
  10. uint32 Bits::Count( uint16 n )
  11.   {
  12.     return count[ Byte0(n) ]
  13.           + count[ Byte1(n) ];
  14.   }
  15.         
  16. uint32 Bits::Count( uint32 n )
  17.   {
  18.     return count[ Byte0(n) ]
  19.           + count[ Byte1(n) ]
  20.           + count[ Byte2(n) ]
  21.           + count[ Byte3(n) ];
  22.   }
  23.  
  24. uint32 Bits::FirstZero( uint16 n )
  25.   {
  26.     if ( Byte0( n ) != 0xff )
  27.         return FirstZero( Byte0( n ) );
  28.     
  29.     return FirstZero( Byte1(n) ) + 8;
  30.  }
  31.         
  32. uint32 Bits::FirstZero( uint32 n )
  33.   {
  34.     if ( Byte0( n ) != 0xff )
  35.         return FirstZero( Byte0( n ) );
  36.     
  37.     if ( Byte1( n ) != 0xff )
  38.         return FirstZero( Byte1(n) ) + 8;
  39.     
  40.     if ( Byte2( n ) != 0xff )
  41.         return FirstZero( Byte2(n) ) + 16;
  42.     
  43.     return FirstZero( Byte3(n) ) + 24;
  44.   }
  45.  
  46. uint32 Bits::LastZero( uint16 n )
  47.   {
  48.     if ( Byte1( n ) != 0xff )
  49.         return LastZero( Byte1( n ) ) + 8;
  50.     
  51.     return LastZero( Byte0(n) );
  52.   }
  53.         
  54. uint32 Bits::LastZero( uint32 n )
  55.   {
  56.     if ( Byte3( n ) != 0xff )
  57.         return LastZero( Byte3( n ) ) + 24;
  58.     
  59.     if ( Byte2( n ) != 0xff )
  60.         return LastZero( Byte2(n) ) + 16;
  61.     
  62.     if ( Byte1( n ) != 0xff )
  63.         return LastZero( Byte1(n) ) + 8;
  64.     
  65.     return LastZero( Byte0(n) );
  66.   }
  67.  
  68. uint16 Bits::Reverse( uint16 n )
  69.   {
  70.     return uint16( Reverse( Byte0( n ) ) ) << 8
  71.           | uint16( Reverse( Byte1( n ) ) );
  72.   }
  73.         
  74. uint32 Bits::Reverse( uint32 n )
  75.   {
  76.     return uint32( Reverse( Byte0( n ) ) ) << 24
  77.           | uint32( Reverse( Byte1( n ) ) ) << 16
  78.           | uint32( Reverse( Byte2( n ) ) ) << 8
  79.           | uint32( Reverse( Byte3( n ) ) );
  80.   }
  81.  
  82. const uint8 Bits::count[ maxuint8 + 1 ] =
  83.   {
  84.     0,1,1,2,  1,2,2,3,  1,2,2,3,  2,3,3,4,
  85.     1,2,2,3,  2,3,3,4,  2,3,3,4,  3,4,4,5,
  86.     1,2,2,3,  2,3,3,4,  2,3,3,4,  3,4,4,5,
  87.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  88.     
  89.     1,2,2,3,  2,3,3,4,  2,3,3,4,  3,4,4,5,
  90.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  91.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  92.     3,4,4,5,  4,5,5,6,  4,5,5,6,  5,6,6,7,
  93.     
  94.     1,2,2,3,  2,3,3,4,  2,3,3,4,  3,4,4,5,
  95.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  96.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  97.     3,4,4,5,  4,5,5,6,  4,5,5,6,  5,6,6,7,
  98.     
  99.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  100.     3,4,4,5,  4,5,5,6,  4,5,5,6,  5,6,6,7,
  101.     3,4,4,5,  4,5,5,6,  4,5,5,6,  5,6,6,7,
  102.     4,5,5,6,  5,6,6,7,  5,6,6,7,  6,7,7,8
  103.   };
  104.  
  105. const uint8 Bits::firstZero[ maxuint8 + 1 ] =
  106.   {
  107.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  108.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,5,
  109.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  110.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,6,
  111.     
  112.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  113.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,5,
  114.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  115.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,7,
  116.  
  117.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  118.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,5,
  119.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  120.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,6,
  121.     
  122.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  123.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,5,
  124.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  125.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,8
  126.   };
  127.  
  128. const uint8 Bits::lastZero[ maxuint8 + 1 ] =
  129.   {
  130.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  131.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  132.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  133.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  134.  
  135.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  136.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  137.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  138.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  139.  
  140.     6,6,6,6,  6,6,6,6,  6,6,6,6,  6,6,6,6,    
  141.     6,6,6,6,  6,6,6,6,  6,6,6,6,  6,6,6,6,    
  142.     6,6,6,6,  6,6,6,6,  6,6,6,6,  6,6,6,6,    
  143.     6,6,6,6,  6,6,6,6,  6,6,6,6,  6,6,6,6,    
  144.  
  145.     5,5,5,5,  5,5,5,5,  5,5,5,5,  5,5,5,5,
  146.     5,5,5,5,  5,5,5,5,  5,5,5,5,  5,5,5,5,
  147.     4,4,4,4,  4,4,4,4,  4,4,4,4,  4,4,4,4,
  148.     3,3,3,3,  3,3,3,3,  2,2,2,2,  1,1,0,8
  149.   };
  150.  
  151. const uint8 Bits::reverse[ maxuint8 + 1 ] =
  152.   {
  153.     0x00,0x80,0x40,0xc0,  0x20,0xa0,0x60,0xe0,  0x10,0x90,0x50,0xd0,  0x30,0xb0,0x70,0xf0,
  154.     0x08,0x88,0x48,0xc8,  0x28,0xa8,0x68,0xe8,  0x18,0x98,0x58,0xd8,  0x38,0xb8,0x78,0xf8,
  155.     0x04,0x84,0x44,0xc4,  0x24,0xa4,0x64,0xe4,  0x14,0x94,0x54,0xd4,  0x34,0xb4,0x74,0xf4,
  156.     0x0c,0x8c,0x4c,0xcc,  0x2c,0xac,0x6c,0xec,  0x1c,0x9c,0x5c,0xdc,  0x3c,0xbc,0x7c,0xfc,
  157.  
  158.     0x02,0x82,0x42,0xc2,  0x22,0xa2,0x62,0xe2,  0x12,0x92,0x52,0xd2,  0x32,0xb2,0x72,0xf2,
  159.     0x0a,0x8a,0x4a,0xca,  0x2a,0xaa,0x6a,0xea,  0x1a,0x9a,0x5a,0xda,  0x3a,0xba,0x7a,0xfa,
  160.     0x06,0x86,0x46,0xc6,  0x26,0xa6,0x66,0xe6,  0x16,0x96,0x56,0xd6,  0x36,0xb6,0x76,0xf6,
  161.     0x0e,0x8e,0x4e,0xce,  0x2e,0xae,0x6e,0xee,  0x1e,0x9e,0x5e,0xde,  0x3e,0xbe,0x7e,0xfe,
  162.  
  163.     0x01,0x81,0x41,0xc1,  0x21,0xa1,0x61,0xe1,  0x11,0x91,0x51,0xd1,  0x31,0xb1,0x71,0xf1,
  164.     0x09,0x89,0x49,0xc9,  0x29,0xa9,0x69,0xe9,  0x19,0x99,0x59,0xd9,  0x39,0xb9,0x79,0xf9,
  165.     0x05,0x85,0x45,0xc5,  0x25,0xa5,0x65,0xe5,  0x15,0x95,0x55,0xd5,  0x35,0xb5,0x75,0xf5,
  166.     0x0d,0x8d,0x4d,0xcd,  0x2d,0xad,0x6d,0xed,  0x1d,0x9d,0x5d,0xdd,  0x3d,0xbd,0x7d,0xfd,
  167.  
  168.     0x03,0x83,0x43,0xc3,  0x23,0xa3,0x63,0xe3,  0x13,0x93,0x53,0xd3,  0x33,0xb3,0x73,0xf3,
  169.     0x0b,0x8b,0x4b,0xcb,  0x2b,0xab,0x6b,0xeb,  0x1b,0x9b,0x5b,0xdb,  0x3b,0xbb,0x7b,0xfb,
  170.     0x07,0x87,0x47,0xc7,  0x27,0xa7,0x67,0xe7,  0x17,0x97,0x57,0xd7,  0x37,0xb7,0x77,0xf7,
  171.     0x0f,0x8f,0x4f,0xcf,  0x2f,0xaf,0x6f,0xef,  0x1f,0x9f,0x5f,0xdf,  0x3f,0xbf,0x7f,0xff
  172.   };
  173.